'''
https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/description/
'''
from functools import cache
from typing import Optional

from utils import TreeNode

class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:

        def f(root):
            if not root:
                return float('inf'), float('-inf'), True, 0, 0
            lmin, lmax, lisbst, lsum, l_max_bst_sum = f(root.left)
            rmin, rmax, risbst, rsum, r_max_bst_sum = f(root.right)
            isbst = lisbst and risbst and lmax < root.val < rmin
            my_sum = root.val + lsum + rsum
            my_max_bst_sum = max(l_max_bst_sum, r_max_bst_sum)
            if isbst:
                my_max_bst_sum = max(my_max_bst_sum, lsum + root.val + rsum)
            return min(lmin, rmin, root.val), max(lmax, rmax, root.val), isbst, my_sum, my_max_bst_sum
        return f(root)[4]
